/*
一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：
'A' -> 1
'B' -> 2
...
'Z' -> 26


"AAJF" ，将消息分组为 (1 1 10 6)
"KJF" ，将消息分组为 (11 10 6)
注意，消息不能分组为  (1 11 06) ，因为 "06" 不能映射为 "F" ，这是由于 "6" 和 "06" 在映射中并不等价。

输入：s = "12"
输出：2
解释：它可以解码为 "AB"（1 2）或者 "L"（12）。

输入：s = "226"
输出：3
解释：它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。
*/

#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
    int numDecodings(string s) {
        int n=s.size();
		vector<int> dp(n+1);
        //dp[0]代表空串
		dp[0]=1;
		for(int i=1;i<=n;i++){
			if(s[i-1]!='0'){
                //只用当前字母解码，那么就把i-1的状态转移过来，因为dp[i]初始化为0，所以dp[i]的值就等于把dp[i-1]的值加过来
				dp[i]+=dp[i-1];
			} 
            //dp是从1开始的，但从s[0]开始，所以 dp[i]对应的是s[i-1]和s[i-2]
			if(i>1 && s[i-2]!='0' && ((s[i-2]-'0')*10+(s[i-1]-'0')<=26)){
				dp[i]+=dp[i-2];
			}
		}
		return dp[n];
    }
};

/*
dp[i]表示字符串s的前i个字符s[1 2 3 ... i]的解码方法
第一种情况：只用s[i]解码，那么只要s[i]!=0，由于前i-1个字符的解码方法数为dp[i-1]
            dp[i]=dp[i-1]
第二种情况：使用两个字母进行解码，即 s[i-1]s[i−1] 和 s[i]s[i] 进行编码。
        与第一种情况类似，s[i-1]s[i−1] 不能等于 0，并且 s[i-1] 和 s[i] 组成的整数必须小于等于 26，
        这样它们就可以被解码成 J∼Z 中的某个字母。


*/